#include <bits/stdc++.h>
using namespace std;

/*
835. 图像重叠
已解答
中等
相关标签
相关企业
给你两个图像 img1 和 img2 ，两个图像的大小都是 n x n ，用大小相同的二进制正方形矩阵表示。二进制矩阵仅由若干 0 和若干 1 组成。

转换 其中一个图像，将所有的 1 向左，右，上，或下滑动任何数量的单位；然后把它放在另一个图像的上面。该转换的 重叠 是指两个图像 都 具有 1 的位置的数目。

请注意，转换 不包括 向任何方向旋转。越过矩阵边界的 1 都将被清除。

最大可能的重叠数量是多少？

 

示例 1：


输入：img1 = [[1,1,0],[0,1,0],[0,1,0]], img2 = [[0,0,0],[0,1,1],[0,0,1]]
输出：3
解释：将 img1 向右移动 1 个单位，再向下移动 1 个单位。

两个图像都具有 1 的位置的数目是 3（用红色标识）。

示例 2：

输入：img1 = [[1]], img2 = [[1]]
输出：1
示例 3：

输入：img1 = [[0]], img2 = [[0]]
输出：0
 

提示：

n == img1.length == img1[i].length
n == img2.length == img2[i].length
1 <= n <= 30
img1[i][j] 为 0 或 1
img2[i][j] 为 0 或 1
*/

// 法一
class Solution {
public:
	int largestOverlap(vector<vector<int>>& img1, vector<vector<int>>& img2) {
		int n = img1.size();
		int maxOverlap = 0;
		for (int dx = -n + 1; dx < n; ++dx) {
			for (int dy = -n + 1; dy < n; ++dy) {
				int overlap = 0;
				for (int i = 0; i < n; ++i) {
					for (int j = 0; j < n; ++j) {
						int ni = i + dy;
						int nj = j + dx;
						if (ni >= 0 && ni < n && nj >= 0 && nj < n &&
							img1[i][j] == 1 && img2[ni][nj] == 1) {
							overlap++;
						}
					}
				}
				maxOverlap = max(maxOverlap, overlap);
			}
		}
		return maxOverlap;
	}
};

// 法二
/**
 * 只记录偏移量，极大优化
 */
class Solution {
public:
	int largestOverlap(vector<vector<int>>& img1, vector<vector<int>>& img2) {
		ios::sync_with_stdio(false);
		cin.tie(0);
		cout.tie(0); // 加速
		int n = img1.size(), diff[2 * n + 1][2 * n + 1];
		memset(diff, 0, sizeof(diff));
		for (int i = 0; i < n; i++) // 遍历图片每个位置去找多少偏移后和它一样
			for (int j = 0; j < n; j++)
				if (img1[i][j] == 1)
					for (int l = 0; l < n; l++)
						for (int m = 0; m < n; m++)
							if (img2[l][m] == 1)
								diff[i - l + n]
									[j - m +
									 n]++; // 偏移位置，这里要+n保证其大于等于0
		int res = 0;
		for (int i = 0; i < 2 * n + 1; i++)
			for (int j = 0; j < 2 * n + 1; j++)
				res = max(res, diff[i][j]); // 找出最大偏移量，就是结果
		return res;
	}
};